/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
export var wiggleSort = function (nums) {
  nums.sort((a, b) => a - b)
  const st = nums.slice()
  const mid = (nums.length - 1) >> 1
  let i = mid,
    j = nums.length - 1
  for (let k = 0; k < nums.length; k++) {
    nums[k] = k % 2 === 0 ? st[i--] : st[j--]
  }
}

export var wiggleSort2 = function (nums) {
  const arr = nums.slice()
  arr.sort((a, b) => a - b)
  const n = nums.length
  const x = Math.floor((n + 1) / 2)
  for (let i = 0, j = x - 1, k = n - 1; i < n; i += 2, j--, k--) {
    nums[i] = arr[j]
    if (i + 1 < n) {
      nums[i + 1] = arr[k]
    }
  }
}

/**
 此方法参考：
 https://leetcode.cn/problems/wiggle-sort-ii/solution/by-fervent-engelbart6at-u85b/
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
export var wiggleSort3 = function (nums) {
  let restart = 1
  function camelSort(nums) {
    restart = 0
    let flag = 1
    for (let i = 0; i < nums.length - 1; ++i) {
      if (nums[i] == nums[i + 1]) {
        let k = i + 2
        while (k < nums.length && nums[k] == nums[i]) ++k
        if (k == nums.length) {
          restart = 1
          k = 0
          while (nums[k] == nums[i]) k += 2
        }
        ;[nums[i + 1], nums[k]] = [nums[k], nums[i + 1]]
      }
      if (flag ^ (nums[i] < nums[i + 1])) {
        ;[nums[i], nums[i + 1]] = [nums[i + 1], nums[i]]
      }
      flag = flag ^ 1
    }
  }
  while (restart) camelSort(nums)
}
